package com.leetcode.根据数据结构分类.栈;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2020/11/20
 * @description: https://leetcode-cn.com/problems/basic-calculator/
 * <p>
 * 实现一个基本的计算器来计算一个简单的字符串表达式的值。
 * 字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格  。
 */
public class C_224_基本计算器 {

	static C_224_基本计算器 action = new C_224_基本计算器();

	/**
	 * 这道题其实也不难，懂了知识点的话，其实就是：中缀转后缀，后转表达式的计算
	 * 昨晚学习了手动转换和算法转换；
	 * 手动转换：1.加括号；2.提取操作符去括号；
	 * 算法转换：按照规则；
	 * --
	 * 由于本题没有乘除，就更简单了！
	 * --
	 * 由于题意理解错了：以为每个 character 都是一个单位！实际上是通过空格分隔的
	 *
	 * @param s
	 * @return
	 */
	public static int calculate(String s) {
		//1.预设置运算符的优先级
		HashMap<Character, Integer> map = new HashMap<>();
		map.put('(', 0);
		map.put(')', 0);
		map.put('+', 1);
		map.put('-', 1);
//		map.put('*',2);
//		map.put('/',2);


		char[] chars = s.toCharArray();
		//操作数栈
		Stack<Character> opeStack = new Stack<>();
		//后缀表达式栈//错了不该是栈，而是队列！
		Queue<Character> postQueue = new LinkedList<>();
		//Stack<Character> postStack = new Stack<>();
		for (int i = 0; i < chars.length; i++) {
			if (chars[i] == ' ') {
				continue;
			}
			//如果是操作符
			if (map.containsKey(chars[i])) {
				//右括号
				if (chars[i] == ')') {
					while (!opeStack.isEmpty() && opeStack.peek() != '(') {
						postQueue.add(opeStack.pop());
					}
					//推出'('
					opeStack.pop();
				} else {

					//如果栈顶元素优先级大于等于 待定元素-> 弹出
					while (chars[i] != '(' && !opeStack.isEmpty() && map.get(opeStack.peek()) >= map.get(chars[i])) {
						postQueue.add(opeStack.pop());
					}
					//否则-> 将待定元素入栈
					opeStack.push(chars[i]);
				}
			} else {
				//数字-> 直接进后缀表达式
				postQueue.add(chars[i]);
			}

		}
		//最后将操作数入栈 后缀
		while (!opeStack.isEmpty()) {
			postQueue.add(opeStack.pop());
		}
		//后缀表达式计算
		//数字栈
		Stack<Integer> intStack = new Stack<>();
		int res = 0;
		//遍历后缀表达式栈
		while (!postQueue.isEmpty()) {
			Character pop = postQueue.poll();
			if (!map.containsKey(pop)) {
				//数字-> 入栈
				intStack.push(Character.getNumericValue(pop));
			} else {
				//进行计算
				int rightNum = intStack.pop();
				int leftNum = intStack.pop();
				int val = calc(leftNum, pop, rightNum);
				intStack.push(val);
			}
		}
		return intStack.pop();
	}

	private static int calc(int left, Character ope, int right) {
		int res = 0;
		switch (ope) {
			case '+':
				res = left + right;
				break;
			case '-':
				res = left - right;
				break;
			case '*':
				res = left * right;
				break;
			case '/':
				res = left / right;
				break;
		}
		return res;
	}

	private static int calc(int left, String ope, int right) {
		int res = 0;
		switch (ope) {
			case "+":
				res = left + right;
				break;
			case "-":
				res = left - right;
				break;
			case "*":
				res = left * right;
				break;
			case "/":
				res = left / right;
				break;
		}
		return res;
	}

	public static void main(String[] args) {
//		test1();
//		test2();
//		test3();
//		test4();
		test5();

		String s = "(";
		System.out.println(s == "(");


		String str = "1 + 1";
		str = "(1+(4+5+2)-3)+(6+8)";
//		str = "2147483647";
//		str = "(1+(4+5+2)-3)+(6+8)";
		int res2 = simpleCalculateOnlyOnePosition(str);
		System.out.println(res2);

	}

	//region	test cases

	static void test1() {
		//2
		String str = "1 + 1";
		int res = action.simpleCalculate(str);
		System.out.println(res);
	}

	static void test2() {
		//12
		String str = "11+1";
		int res = action.simpleCalculate(str);
		System.out.println(res);
	}

	static void test3() {
		//12
		String str = "11 + 1";
		int res = action.simpleCalculate(str);
		System.out.println(res);
	}

	static void test4() {
		// 3
		String str = " 2-1 + 2 ";
		int res = action.simpleCalculate(str);
		System.out.println(res);
	}

	static void test5() {
		// 23
		String str = "(1+(4+5+2)-3)+(6+8)";
		int res = action.simpleCalculate(str);
		System.out.println(res);
	}


	//endregion


	public static int calculate2(String s) {
		HashMap map = getMap();
		char[] chars = s.toCharArray();
		//1.存放真实的数据
		String[] strArr = new String[chars.length];
		//记录真实数据的大小
		int size = 0;
		int index = 0;
		for (int i = 0; i < chars.length; i++) {
			if (chars[i] == ' ') {
				continue;
			}
			//如果是操作数，直接保留
			if (map.containsKey(chars[i])) {
				strArr[index++] = chars[i] + "";
			} else {
				int j = i;
				String temp = chars[i] + "";
				//如果是数字需要判断下一个
				while (j < chars.length - 1 && chars[j + 1] != ' ' && !map.containsKey(chars[j + 1])) {
					j++;
					temp += chars[j];
				}
				strArr[index++] = temp;
				i = j;
			}
		}
		size = index;


		HashMap<String, Integer> nMap = getStringMap();
		//2.中缀转后缀
		Stack<String> opeStack = new Stack<>();
		//后缀表达式栈//错了不该是栈，而是队列！
		Queue<String> postQueue = new LinkedList<>();
		//Stack<Character> postStack = new Stack<>();
		for (int i = 0; i < size; i++) {
			//如果是操作符
			if (nMap.containsKey(strArr[i])) {
				//右括号
				if (strArr[i].equals(")")) {
					while (!opeStack.isEmpty() && !opeStack.peek().equals("(")) {
						postQueue.add(opeStack.pop());
					}
					//推出'('
					opeStack.pop();
				} else {

					//如果栈顶元素优先级大于等于 待定元素-> 弹出
					while (!strArr[i].equals("(") && !opeStack.isEmpty() && nMap.get(opeStack.peek()) >= nMap.get(strArr[i])) {
						postQueue.add(opeStack.pop());
					}
					//否则-> 将待定元素入栈
					opeStack.push(strArr[i]);
				}
			} else {
				//数字-> 直接进后缀表达式
				postQueue.add(strArr[i]);
			}

		}
		//最后将操作数入栈 后缀
		while (!opeStack.isEmpty()) {
			postQueue.add(opeStack.pop());
		}
		//后缀表达式计算
		//数字栈
		Stack<Integer> intStack = new Stack<>();
		//遍历后缀表达式栈
		while (!postQueue.isEmpty()) {
			String pop = postQueue.poll();
			if (!nMap.containsKey(pop)) {
				//数字-> 入栈
				intStack.push(Integer.parseInt(pop));
			} else {
				//进行计算
				int rightNum = intStack.pop();
				int leftNum = intStack.pop();
				int val = calc(leftNum, pop, rightNum);
				intStack.push(val);
			}
		}
		return intStack.pop();
	}

	public static HashMap getMap() {
		HashMap<Character, Integer> map = new HashMap<>();
		map.put('(', 0);
		map.put(')', 0);
		map.put('+', 1);
		map.put('-', 1);
		return map;
	}

	public static HashMap getStringMap() {
		HashMap<String, Integer> map = new HashMap<>();
		map.put("(", 0);
		map.put(")", 0);
		map.put("+", 1);
		map.put("-", 1);
		return map;
	}


	/**
	 * 由于木有优先级，可以直接使用一个栈即可
	 * 但是仍然需要考虑非一位数！
	 *
	 * @param s
	 * @return
	 */
	public static int simpleCalculateOnlyOnePosition(String s) {
		char[] chars = s.toCharArray();
		int len = chars.length;
		ArrayDeque<Character> digitDeque = new ArrayDeque<>(len);
		for (int i = 0; i < len; i++) {
			if (chars[i] == ' ') {
				continue;
			}
			//如果本次是一个数字
			if (Character.isDigit(chars[i])) {
				if (!digitDeque.isEmpty()) {
					if (digitDeque.peekLast() == '+') {
						digitDeque.removeLast();
						char c = addOpe(digitDeque.removeLast(), chars[i]);
						digitDeque.addLast(c);
					} else if (digitDeque.peekLast() == '-') {
						digitDeque.removeLast();
						char c = minusOpe(digitDeque.removeLast(), chars[i]);
						digitDeque.addLast(c);
					} else {
						digitDeque.addLast(chars[i]);
					}
				} else {
					digitDeque.addLast(chars[i]);
				}
			} else if (chars[i] == '(') {
				digitDeque.addLast('(');
			} else if (chars[i] == ')') {
				//此时剩下右括号
				if (digitDeque.peekLast() != '(') {
					char c = digitDeque.removeLast();
					//移除左括号
					digitDeque.removeLast();
					//作为新的元素进行添加
					chars[i--] = c;
				} else {
					digitDeque.removeLast();
				}
			} else {
				digitDeque.addLast(chars[i]);
			}
		}
		return Character.getNumericValue(digitDeque.removeFirst());
	}

	private static char minusOpe(char first, char second) {
		return (char) ((Character.getNumericValue(first) - Character.getNumericValue(second)) + 48
		);
	}

	/**
	 * 超过了 10 进制就不准了
	 *
	 * @param first
	 * @param second
	 * @return
	 */
	private static char addOpe(char first, char second) {
		return (char) ((Character.getNumericValue(first) + Character.getNumericValue(second)) + 48
		);
	}

	/**
	 * 数字、'+'、'-'、'('、')'、和 ' '
	 * 本题不用考虑越界：s.length() <= 3*10^5
	 * 2 - 1 + 2
	 * --
	 * 错在：不能一次性地从尾到头进行计算；否则就相当于在后面地位置给加了一个括号
	 *
	 * @param s
	 * @return
	 */
	public int simpleCalculateFail(String s) {
		char[] chars = s.toCharArray();
		int len = chars.length;
		int value = 0;
		//标记 是否已经产生了数字
		boolean flag = false;

		//数字栈
		ArrayDeque<Integer> digitDeque = new ArrayDeque<>(len);
		ArrayDeque<Character> opeDeque = new ArrayDeque<>(len);
		for (int i = 0; i < len; i++) {
			if (Character.isDigit(chars[i])) {
				value = value * 10 + Character.getNumericValue(chars[i]);
				flag = true;
			} else {
				//此时已经得到一个有意义的数字

				//如果需要每一个都运算的话，似乎是安排一遍，那么就干脆等到 ) 时再处理吧
				if (chars[i] == ')') {
					//此时 必然 ope 有
					//此时计算至 ( 的位置
					while (opeDeque.peekLast() != '(') {
						//'+'、'-'
						if (opeDeque.removeLast() == '+') {
							value = addOnce(digitDeque.removeLast(), value);
						} else {
							value = minusOnce(digitDeque.removeLast(), value);
						}
					}
					digitDeque.addLast(value);
					// remove (
					opeDeque.removeLast();
				} else if (chars[i] == ' ') {
					//do nothing
					if (flag) {
						digitDeque.addLast(value);
					}

				} else {
					if (flag) {
						digitDeque.addLast(value);
					}
					opeDeque.addLast(chars[i]);
				}


				value = 0;
				flag = false;
			}
		}

		//最后计算去了括号里的值
		while (!opeDeque.isEmpty()) {
			if (opeDeque.removeLast() == '+') {
				value = addOnce(digitDeque.removeLast(), value);
			} else {
				value = minusOnce(digitDeque.removeLast(), value);
			}
		}
		return value;
	}

	private int minusOnce(int first, int second) {
		return first - second;
	}

	private int addOnce(int first, int second) {
		return first + second;
	}


	/**
	 * 靠着硬业务强行通过了！
	 * 由于木有优先级：即时计算！
	 * 不过官方题解真是巧。
	 *
	 * @param s
	 * @return
	 */
	private int simpleCalculate(String s) {
		char[] chars = s.toCharArray();
		int len = chars.length;
		int value = 0;
		//标记 是否已经产生了数字
		boolean flag = false;

		//数字栈
		ArrayDeque<Integer> digitDeque = new ArrayDeque<>(len);
		ArrayDeque<Character> opeDeque = new ArrayDeque<>(len);
		for (int i = 0; i < len; i++) {
			if (Character.isDigit(chars[i])) {
				value = value * 10 + Character.getNumericValue(chars[i]);
				flag = true;
			} else {
				//即时计算符号数
				if (opeDeque.isEmpty()) {
					//不用计算
					if (flag) {
						digitDeque.addLast(value);
					}
				} else {
					//处理之前地
					if (flag) {
						while (!opeDeque.isEmpty() && opeDeque.peekLast() != '(') {
							if (opeDeque.removeLast() == '+') {
								value = addOnce(digitDeque.removeLast(), value);
							} else {
								value = minusOnce(digitDeque.removeLast(), value);
							}
						}
						digitDeque.addLast(value);
					}

				}
				//处理当前地
				if (chars[i] == ' ') {

				} else if (chars[i] == ')') {
					//此时 必然 ope 有
					//此时计算至 ( 的位置
					if (opeDeque.peekLast() == '(') {
						opeDeque.removeLast();
					} else {
						while (opeDeque.peekLast() != '(') {
							//'+'、'-'
							if (opeDeque.removeLast() == '+') {
								value = addOnce(digitDeque.removeLast(), value);
							} else {
								value = minusOnce(digitDeque.removeLast(), value);
							}
						}
						digitDeque.addLast(value);
						// remove (
						opeDeque.removeLast();
					}
					//继续之前地计算(由于 flag = false ，所以下一次循环时不会先计算先前地)
					if (!opeDeque.isEmpty() && opeDeque.peekLast() != '(') {
						do {
							int second = digitDeque.removeLast();
							if (opeDeque.removeLast() == '+') {
								value = addOnce(digitDeque.removeLast(), second);
							} else {
								value = minusOnce(digitDeque.removeLast(), second);
							}
						} while (!opeDeque.isEmpty() && opeDeque.peekLast() != '(');
						digitDeque.addLast(value);
					}

				} else {
					//（ + -
					opeDeque.addLast(chars[i]);
					if (digitDeque.isEmpty() && chars[i]!='('){
						digitDeque.addLast(0);
					}
				}

				value = 0;
				flag = false;
			}
		}

		while (!opeDeque.isEmpty()) {
			if (opeDeque.removeLast() == '+') {
				value = addOnce(digitDeque.removeLast(), value);
			} else {
				value = minusOnce(digitDeque.removeLast(), value);
			}
			digitDeque.addLast(value);
		}
		return digitDeque.isEmpty()? value:digitDeque.removeFirst();
	}


}
